Boolean algebra

mathematics, logic (After the logician George Boole)

1. Commonly, and especially in computer science and digital

electronics, this term is used to mean two-valued logic.

2. This is in stark contrast with the definition used by pure

mathematicians who in the 1960s introduced "Boolean-valued

models" into logic precisely because a "Boolean-valued

model" is an interpretation of a theory that allows more

than two possible truth values!

Strangely, a Boolean algebra (in the mathematical sense) is

not strictly an algebra, but is in fact a lattice. A

Boolean algebra is sometimes defined as a "complemented

distributive lattice".

Boole's work which inspired the mathematical definition

concerned algebras of sets, involving the operations of

intersection, union and complement on sets. Such algebras

obey the following identities where the operators ^, V, - and

constants 1 and 0 can be thought of either as set

intersection, union, complement, universal, empty; or as

two-valued logic AND, OR, NOT, TRUE, FALSE; or any other

conforming system.

a ^ b = b ^ a a V b = b V a (commutative laws)

(a ^ b) ^ c = a ^ (b ^ c)

(a V b) V c = a V (b V c) (associative laws)

a ^ (b V c) = (a ^ b) V (a ^ c)

a V (b ^ c) = (a V b) ^ (a V c) (distributive laws)

a ^ a = a a V a = a (idempotence laws)

--a = a

-(a ^ b) = (-a) V (-b)

-(a V b) = (-a) ^ (-b) (de Morgan's laws)

a ^ -a = 0 a V -a = 1

a ^ 1 = a a V 0 = a

a ^ 0 = 0 a V 1 = 1

-1 = 0 -0 = 1

There are several common alternative notations for the "-" or

logical complement operator.

If a and b are elements of a Boolean algebra, we define a #@= b

to mean that a ^ b = a, or equivalently a V b = b. Thus, for

example, if ^, V and - denote set intersection, union and

complement then #@= is the inclusive subset relation. The

relation #@= is a partial ordering, though it is not

necessarily a linear ordering since some Boolean algebras

contain incomparable values.

Note that these laws only refer explicitly to the two

distinguished constants 1 and 0 (sometimes written as LaTeX

top and bot), and in two-valued logic there are no others,

but according to the more general mathematical definition, in

some systems variables a, b and c may take on other values as

well.

(1997-02-27)